﻿#define _CRT_SECURE_NO_WARNINGS

//template<class K
//struct HashFun
//{
//	size_t operator()(const K& key)
//	{
//		return (size_t)key;
//	}
//};
//
//// 特化 
//template<>
//struct HashFunc<string>
//{
//	// 字符串转换成整形，可以把字符ascii码相加即可
//	// 但是直接相加的话，类似"abcd"和"bcad"这样的字符串计算出是相同的
//	// 这里使用BKDR哈希的思路，用上次的计算结果去乘以⼀个质数，这个质数⼀般取31, 131等效果会⽐较好
//		size_t operator()(const string& key)
//		{
//		size_t hash = 0;
//		for (auto e : key)
//		{
//			hash *= 131;
//			hash += e;
//		}
//		return hash;
//		}
//};
//
//template<class K, class V, class Hash = HashFunc<K>>
//class HashTable
//{
//public:
//	// 功能实现...
//
//private:
//	vector<HashData<K, V>> _tables;
//	size_t _n = 0; // 表中存储数据个数 
//};


// 开散列
namespace BucketHash
{
	// 哈希表的节点结构：单链表
	template<class K, class V>
	struct HashNode
	{
		pair<K, V> _kv;
		HashNode<K, V>* next;

		HashNode(const pair<K, V>& kv)
			: _kv(kv)
			, next(nullptr)
		{}
	};

	// 哈希表的仿函数
	template<class K>
	struct HashFunc
	{
		size_t operator()(const K& key)
		{
			return (size_t)key;
		}
	};

	// string类模板特化
	template<>
	struct HashFunc<string>
	{
		// 字符串转换成整形，可以把字符ascii码相加即可
		// 但是直接相加的话，类似"abcd"和"bcad"这样的字符串计算出是相同的
		// 这里使用BKDR哈希的思路，用上次的计算结果去乘以⼀个质数，这个质数⼀般取31, 131等效果会比较好
		size_t operator()(const string& key)
		{
			size_t hash = 0;
			for (auto e : key)
			{
				hash *= 131;
				hash += e;
			}

			return hash;
		}
	};


	// 哈希表
	template<class K, class V, class Hash = HashFunc<K>>
	class HashTable
	{
		typedef HashNode<K, V> Node;

		inline unsigned long __stl_next_prime(unsigned long n)
		{
			// Note: assumes long is at least 32 bits.
			static const int __stl_num_primes = 28;
			static const unsigned long __stl_prime_list[__stl_num_primes] =
			{
				53, 97, 193, 389, 769,
				1543, 3079, 6151, 12289, 24593,
				49157, 98317, 196613, 393241, 786433,
				1572869, 3145739, 6291469, 12582917, 25165843,
				50331653, 100663319, 201326611, 402653189, 805306457,
				1610612741, 3221225473, 4294967291
			};

			const unsigned long* first = __stl_prime_list;
			const unsigned long* last = __stl_prime_list + __stl_num_primes;
			const unsigned long* pos = lower_bound(first, last, n);

			return pos == last ? *(last - 1) : *pos;
		}

	public:
		HashTable()
		{
			_tables.resize(__stl_next_prime(0), nullptr);
		}

		~HashTable()
		{
			// 依次把每个桶释放 
			for (size_t i = 0; i < _tables.size(); i++)
			{
				Node* cur = _tables[i];
				while (cur)
				{
					Node* next = cur->_next;
					delete cur;
					cur = next;
				}
				_tables[i] = nullptr;
			}
		}

		//插入
		bool insert(const pair<K, V>& kv)
		{
			if (find(kv.first))
				return false;

			//扩容--当载荷因子达到1时我们进行扩容
			if (_n == _tables.size())
			{
				vector<Node*> newtables(__stl_next_prime(_tables.size() + 1), nullptr);
				for (size_t i = 0; i < _tables.size(); ++i)
				{
					Node* cur = _tables[i];
					while (cur)
					{
						Node* next = cur->next;

						//重新计算映射关系，调用仿函数的匿名对象来将key转换为整数
						size_t hashi = Hash()(cur->_kv.first) % newTables.size();
						// 头插到新表
						cur->next = newTables[hashi];
						newTables[hashi] = cur;

						cur = next;
					}

					_tables[i] = nullptr;
				}

				_tables.swap(newTables);
			}

			//调用仿函数的匿名对象来将key转换为整数
			size_t hashi = Hash()(kv.first) % _tables.size();
			//哈希桶头插
			Node* newNode = new Node(kv);
			newNode->next = _tables[hashi];
			_tables[hashi] = newNode;
			++_n;

			return true;
		}
		
		// 查找
		Node* Find(const K& key)
		{
			size_t hashi = Hash()(key) % _tables.size();
			Node* cur = _tables[hashi];
			while (cur)
			{
				if (cur->_kv.first == key)
					return cur;
				cur = cur->next;
			}

			return nullptr;
		}

		// 删除
		bool Erase(const K& key)
		{
			// 由于单链表中删除节点需要改变上一个节点的指向，所以这里不能find后直接erase
			size_t hashi = Hash()(key) % _tables.size();
			Node* prev = nullptr;
			Node* cur = _tables[hashi];
			while (cur)
			{
				// 删除还要分是否为头结点
				if (cur->_kv.first == key)
				{
					// 头删
					if (cur == _tables[hashi])
						_tables[hashi] = cur->next;
					else
						prev->next = cur->next;

					delete cur;
					--_n;
					return true;
				}

				// 迭代
				prev = cur;
				cur = cur->next;
			}

			return false;
		}

	private:
		vector<Node*> _tables;  // 指针数组
		size_t _n;  			// 表中有效数据的个数
	};
}

